class Solution {
public:
    /**
     * @param nums: An array of integers
     * @return: An integer
     */
    // int maxProduct(vector<int> &nums) {
    //     int n = nums.size();
    //     vector<int> res(n, INT_MIN); //res[i]表示以i结尾最大的连乘，不然后面转移方程不能直接乘上去
    //     vector<int> res_min(n, INT_MAX);
    //     int ans = nums[0];
    //     res[0] = ans;
    //     res_min[0] = ans;
    //     for (int i = 1; i < n; ++i) {
    //         res[i] = max(max(res[i - 1] * nums[i], res_min[i - 1] * nums[i]), nums[i]);
    //         res_min[i] = min(min(res[i - 1] * nums[i], res_min[i - 1] * nums[i]), nums[i]);
    //         ans = max(ans, res[i]);
    //     }
    //     return ans;
    // }

    // 法二：贪心。如果是负数导致的变小，那么可以从第一个负数后面开始乘看能不能更大。所以从第一个负数之后开始记就行。
    // 注意遇到0重新开始
    int maxProduct(vector<int> &nums) {
        int res = INT_MIN;
        int tmp = 1;
        int neg_res = 0;
        for (int i = 0; i < nums.size(); ++i) {
            tmp *= nums[i];
            res = max(res, tmp);
            if (neg_res != 0) {
                neg_res *= nums[i];
                res = max(res, neg_res);
            } else if (nums[i] < 0) {
                neg_res = 1;
            }
            // res = max(res, neg_res); 注意一开始neg_res赋予的1不算
            if (nums[i] == 0) {
                tmp = 1;
                neg_res = 0;
            }
        }
        return res;
    }
};